1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
3 {\ttfamily \raggedright {
5 \mbox{}\textbf{\textcolor{RoyalBlue
}{\#include
}}\
\texttt{\textcolor{Red
}{$<$iostream$>$
}} \\
6 \mbox{}\textbf{\textcolor{RoyalBlue
}{\#include
}}\
\texttt{\textcolor{Red
}{$<$vector$>$
}} \\
7 \mbox{}\textbf{\textcolor{RoyalBlue
}{\#include
}}\
\texttt{\textcolor{Red
}{$<$algorithm$>$
}} \\
9 \mbox{}\textbf{\textcolor{Blue
}{using
}}\
\textbf{\textcolor{Blue
}{namespace
}}\ std
\textcolor{BrickRed
}{;
} \\
11 \mbox{}\textit{\textcolor{Brown
}{/*
}} \\
12 \mbox{}\textit{\textcolor{Brown
}{Algoritmo\ de\ Kruskal,\ para\ encontrar\ el\ árbol\ de\ recubrimiento\ de\ mínima\ suma.
}} \\
13 \mbox{}\textit{\textcolor{Brown
}{*/
}} \\
15 \mbox{}\textbf{\textcolor{Blue
}{struct
}}\ edge
\textcolor{Red
}{\
{} \\
16 \mbox{}\ \
\textcolor{ForestGreen
}{int
}\ start
\textcolor{BrickRed
}{,
}\ end
\textcolor{BrickRed
}{,
}\ weight
\textcolor{BrickRed
}{;
} \\
17 \mbox{}\ \
\textcolor{ForestGreen
}{bool
}\
\textbf{\textcolor{Blue
}{operator
}}\
\textcolor{BrickRed
}{$<$
}\
\textcolor{BrickRed
}{(
}\textbf{\textcolor{Blue
}{const
}}\ edge\
\textcolor{BrickRed
}{\&
}that
\textcolor{BrickRed
}{)
}\
\textbf{\textcolor{Blue
}{const
}}\
\textcolor{Red
}{\
{} \\
18 \mbox{}\ \ \ \
\textit{\textcolor{Brown
}{//Si\ se\ desea\ encontrar\ el\ árbol\ de\ recubrimiento\ de\ máxima\ suma,\ cambiar\ el\ $<$\ por\ un\ $>$
}} \\
19 \mbox{}\ \ \ \
\textbf{\textcolor{Blue
}{return
}}\ weight\
\textcolor{BrickRed
}{$<$
}\ that
\textcolor{BrickRed
}{.
}weight
\textcolor{BrickRed
}{;
} \\
20 \mbox{}\ \
\textcolor{Red
}{\
}} \\
21 \mbox{}\textcolor{Red
}{\
}}\textcolor{BrickRed
}{;
} \\
24 \mbox{}\textit{\textcolor{Brown
}{/*\ Union\ find\ */
}} \\
25 \mbox{}\textcolor{ForestGreen
}{int
}\ p
\textcolor{BrickRed
}{[}\textcolor{Purple
}{10001}\textcolor{BrickRed
}{],
}\ rank
\textcolor{BrickRed
}{[}\textcolor{Purple
}{10001}\textcolor{BrickRed
}{];
} \\
26 \mbox{}\textcolor{ForestGreen
}{void
}\
\textbf{\textcolor{Black
}{make$
\_$set
}}\textcolor{BrickRed
}{(
}\textcolor{ForestGreen
}{int
}\ x
\textcolor{BrickRed
}{)
}\textcolor{Red
}{\
{}\ p
\textcolor{BrickRed
}{[}x
\textcolor{BrickRed
}{]}\
\textcolor{BrickRed
}{=
}\ x
\textcolor{BrickRed
}{,
}\ rank
\textcolor{BrickRed
}{[}x
\textcolor{BrickRed
}{]}\
\textcolor{BrickRed
}{=
}\
\textcolor{Purple
}{0}\textcolor{BrickRed
}{;
}\
\textcolor{Red
}{\
}} \\
27 \mbox{}\textcolor{ForestGreen
}{void
}\
\textbf{\textcolor{Black
}{link
}}\textcolor{BrickRed
}{(
}\textcolor{ForestGreen
}{int
}\ x
\textcolor{BrickRed
}{,
}\
\textcolor{ForestGreen
}{int
}\ y
\textcolor{BrickRed
}{)
}\textcolor{Red
}{\
{}\ rank
\textcolor{BrickRed
}{[}x
\textcolor{BrickRed
}{]}\
\textcolor{BrickRed
}{$>$
}\ rank
\textcolor{BrickRed
}{[}y
\textcolor{BrickRed
}{]}\
\textcolor{BrickRed
}{?
}\ p
\textcolor{BrickRed
}{[}y
\textcolor{BrickRed
}{]}\
\textcolor{BrickRed
}{=
}\ x\
\textcolor{BrickRed
}{:
}\ p
\textcolor{BrickRed
}{[}x
\textcolor{BrickRed
}{]}\
\textcolor{BrickRed
}{=
}\ y
\textcolor{BrickRed
}{,
}\ rank
\textcolor{BrickRed
}{[}x
\textcolor{BrickRed
}{]}\
\textcolor{BrickRed
}{==
}\ rank
\textcolor{BrickRed
}{[}y
\textcolor{BrickRed
}{]}\
\textcolor{BrickRed
}{?
}\ rank
\textcolor{BrickRed
}{[}y
\textcolor{BrickRed
}{]++:
}\
\textcolor{Purple
}{0}\textcolor{BrickRed
}{;
}\
\textcolor{Red
}{\
}} \\
28 \mbox{}\textcolor{ForestGreen
}{int
}\
\textbf{\textcolor{Black
}{find$
\_$set
}}\textcolor{BrickRed
}{(
}\textcolor{ForestGreen
}{int
}\ x
\textcolor{BrickRed
}{)
}\textcolor{Red
}{\
{}\
\textbf{\textcolor{Blue
}{return
}}\ x\
\textcolor{BrickRed
}{!=
}\ p
\textcolor{BrickRed
}{[}x
\textcolor{BrickRed
}{]}\
\textcolor{BrickRed
}{?
}\ p
\textcolor{BrickRed
}{[}x
\textcolor{BrickRed
}{]}\
\textcolor{BrickRed
}{=
}\
\textbf{\textcolor{Black
}{find$
\_$set
}}\textcolor{BrickRed
}{(
}p
\textcolor{BrickRed
}{[}x
\textcolor{BrickRed
}{])
}\
\textcolor{BrickRed
}{:
}\ p
\textcolor{BrickRed
}{[}x
\textcolor{BrickRed
}{];
}\
\textcolor{Red
}{\
}} \\
29 \mbox{}\textcolor{ForestGreen
}{void
}\
\textbf{\textcolor{Black
}{merge
}}\textcolor{BrickRed
}{(
}\textcolor{ForestGreen
}{int
}\ x
\textcolor{BrickRed
}{,
}\
\textcolor{ForestGreen
}{int
}\ y
\textcolor{BrickRed
}{)
}\textcolor{Red
}{\
{}\
\textbf{\textcolor{Black
}{link
}}\textcolor{BrickRed
}{(
}\textbf{\textcolor{Black
}{find$
\_$set
}}\textcolor{BrickRed
}{(
}x
\textcolor{BrickRed
}{),
}\
\textbf{\textcolor{Black
}{find$
\_$set
}}\textcolor{BrickRed
}{(
}y
\textcolor{BrickRed
}{));
}\
\textcolor{Red
}{\
}} \\
30 \mbox{}\textit{\textcolor{Brown
}{/*\ End\ union\ find\ */
}} \\
33 \mbox{}\textcolor{ForestGreen
}{int
}\
\textbf{\textcolor{Black
}{main
}}\textcolor{BrickRed
}{()
}\textcolor{Red
}{\
{} \\
34 \mbox{}\ \
\textcolor{ForestGreen
}{int
}\ c
\textcolor{BrickRed
}{;
} \\
35 \mbox{}\ \ cin\
\textcolor{BrickRed
}{$>$$>$
}\ c
\textcolor{BrickRed
}{;
} \\
36 \mbox{}\ \
\textbf{\textcolor{Blue
}{while
}}\
\textcolor{BrickRed
}{(
}c
\textcolor{BrickRed
}{-\/-)
}\textcolor{Red
}{\
{} \\
37 \mbox{}\ \ \ \
\textcolor{ForestGreen
}{int
}\ n
\textcolor{BrickRed
}{,
}\ m
\textcolor{BrickRed
}{;
} \\
38 \mbox{}\ \ \ \ cin\
\textcolor{BrickRed
}{$>$$>$
}\ n\
\textcolor{BrickRed
}{$>$$>$
}\ m
\textcolor{BrickRed
}{;
} \\
39 \mbox{}\ \ \ \ vector
\textcolor{BrickRed
}{$<$
}edge
\textcolor{BrickRed
}{$>$
}\ e
\textcolor{BrickRed
}{;
} \\
40 \mbox{}\ \ \ \
\textcolor{ForestGreen
}{long
}\
\textcolor{ForestGreen
}{long
}\ total\
\textcolor{BrickRed
}{=
}\
\textcolor{Purple
}{0}\textcolor{BrickRed
}{;
} \\
41 \mbox{}\ \ \ \
\textbf{\textcolor{Blue
}{while
}}\
\textcolor{BrickRed
}{(
}m
\textcolor{BrickRed
}{-\/-)
}\textcolor{Red
}{\
{} \\
42 \mbox{}\ \ \ \ \ \ edge\ t
\textcolor{BrickRed
}{;
} \\
43 \mbox{}\ \ \ \ \ \ cin\
\textcolor{BrickRed
}{$>$$>$
}\ t
\textcolor{BrickRed
}{.
}start\
\textcolor{BrickRed
}{$>$$>$
}\ t
\textcolor{BrickRed
}{.
}end\
\textcolor{BrickRed
}{$>$$>$
}\ t
\textcolor{BrickRed
}{.
}weight
\textcolor{BrickRed
}{;
} \\
44 \mbox{}\ \ \ \ \ \ e
\textcolor{BrickRed
}{.
}\textbf{\textcolor{Black
}{push$
\_$back
}}\textcolor{BrickRed
}{(
}t
\textcolor{BrickRed
}{);
} \\
45 \mbox{}\ \ \ \ \ \ total\
\textcolor{BrickRed
}{+=
}\ t
\textcolor{BrickRed
}{.
}weight
\textcolor{BrickRed
}{;
} \\
46 \mbox{}\ \ \ \
\textcolor{Red
}{\
}} \\
47 \mbox{}\ \ \ \
\textbf{\textcolor{Black
}{sort
}}\textcolor{BrickRed
}{(
}e
\textcolor{BrickRed
}{.
}\textbf{\textcolor{Black
}{begin
}}\textcolor{BrickRed
}{(),
}\ e
\textcolor{BrickRed
}{.
}\textbf{\textcolor{Black
}{end
}}\textcolor{BrickRed
}{());
} \\
48 \mbox{}\ \ \ \
\textbf{\textcolor{Blue
}{for
}}\
\textcolor{BrickRed
}{(
}\textcolor{ForestGreen
}{int
}\ i
\textcolor{BrickRed
}{=
}\textcolor{Purple
}{0}\textcolor{BrickRed
}{;
}\ i
\textcolor{BrickRed
}{$<$=
}n
\textcolor{BrickRed
}{;
}\
\textcolor{BrickRed
}{++
}i
\textcolor{BrickRed
}{)
}\textcolor{Red
}{\
{} \\
49 \mbox{}\ \ \ \ \ \
\textbf{\textcolor{Black
}{make$
\_$set
}}\textcolor{BrickRed
}{(
}i
\textcolor{BrickRed
}{);
} \\
50 \mbox{}\ \ \ \
\textcolor{Red
}{\
}} \\
51 \mbox{}\ \ \ \
\textbf{\textcolor{Blue
}{for
}}\
\textcolor{BrickRed
}{(
}\textcolor{ForestGreen
}{int
}\ i
\textcolor{BrickRed
}{=
}\textcolor{Purple
}{0}\textcolor{BrickRed
}{;
}\ i
\textcolor{BrickRed
}{$<$
}e
\textcolor{BrickRed
}{.
}\textbf{\textcolor{Black
}{size
}}\textcolor{BrickRed
}{();
}\
\textcolor{BrickRed
}{++
}i
\textcolor{BrickRed
}{)
}\textcolor{Red
}{\
{} \\
52 \mbox{}\ \ \ \ \ \
\textcolor{ForestGreen
}{int
}\ u\
\textcolor{BrickRed
}{=
}\ e
\textcolor{BrickRed
}{[}i
\textcolor{BrickRed
}{].
}start
\textcolor{BrickRed
}{,
}\ v\
\textcolor{BrickRed
}{=
}\ e
\textcolor{BrickRed
}{[}i
\textcolor{BrickRed
}{].
}end
\textcolor{BrickRed
}{,
}\ w\
\textcolor{BrickRed
}{=
}\ e
\textcolor{BrickRed
}{[}i
\textcolor{BrickRed
}{].
}weight
\textcolor{BrickRed
}{;
} \\
53 \mbox{}\ \ \ \ \ \
\textbf{\textcolor{Blue
}{if
}}\
\textcolor{BrickRed
}{(
}\textbf{\textcolor{Black
}{find$
\_$set
}}\textcolor{BrickRed
}{(
}u
\textcolor{BrickRed
}{)
}\
\textcolor{BrickRed
}{!=
}\
\textbf{\textcolor{Black
}{find$
\_$set
}}\textcolor{BrickRed
}{(
}v
\textcolor{BrickRed
}{))
}\textcolor{Red
}{\
{} \\
54 \mbox{}\ \ \ \ \ \ \ \
\textit{\textcolor{Brown
}{//printf("
{}Joining\ \%d\ with\ \%d\ using\ weight\ \%d
\textbackslash{}n"
{},\ u,\ v,\ w);
}} \\
55 \mbox{}\ \ \ \ \ \ \ \ total\
\textcolor{BrickRed
}{-=
}\ w
\textcolor{BrickRed
}{;
} \\
56 \mbox{}\ \ \ \ \ \ \ \
\textbf{\textcolor{Black
}{merge
}}\textcolor{BrickRed
}{(
}u
\textcolor{BrickRed
}{,
}\ v
\textcolor{BrickRed
}{);
} \\
57 \mbox{}\ \ \ \ \ \
\textcolor{Red
}{\
}} \\
58 \mbox{}\ \ \ \
\textcolor{Red
}{\
}} \\
59 \mbox{}\ \ \ \ cout\
\textcolor{BrickRed
}{$<$$<$
}\ total\
\textcolor{BrickRed
}{$<$$<$
}\ endl
\textcolor{BrickRed
}{;
} \\
61 \mbox{}\ \
\textcolor{Red
}{\
}} \\
62 \mbox{}\ \
\textbf{\textcolor{Blue
}{return
}}\
\textcolor{Purple
}{0}\textcolor{BrickRed
}{;
} \\
63 \mbox{}\textcolor{Red
}{\
}} \\
65 } \normalfont\normalsize